package com.github.yangyishe.p100;

import java.util.Arrays;

/**
 * 31. 下一个排列
 * https://leetcode.cn/problems/next-permutation/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * 整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。
 *
 * 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
 * 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
 *
 * 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
 * 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
 * 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
 * 给你一个整数数组 nums ，找出 nums 的下一个排列。
 *
 * 必须 原地 修改，只允许使用额外常数空间。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3]
 * 输出：[1,3,2]
 * 示例 2：
 *
 * 输入：nums = [3,2,1]
 * 输出：[1,2,3]
 * 示例 3：
 *
 * 输入：nums = [1,1,5]
 * 输出：[1,5,1]
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 100
 * 0 <= nums[i] <= 100
 */
public class Problem31 {
    public static void main(String[] args) {
        int[] nums=new int[]{2,4,3,3,1};

        Problem31 problem31 = new Problem31();
        problem31.nextPermutation(nums);
        System.out.println("Arrays.toString(nums) = " + Arrays.toString(nums));

    }

    /**
     * 思路：
     * 规律总结如下：
     * 从最右端的数字开始向左遍历，如果第一次遇到左边的数字比右边的数字大（该左边的数字，记为最右升起位），
     * 则如果存在下一个更大的序列，必定是：
     * 1. 最右升起位，以左的数字（不含最右升起位），所有数字的位置不变；（因为必然可以构建出更大的，且左侧数字不变的序列）
     * 2. 最右升起位，以右的数字（含最右升起位），构建为新的比当前序列仅大的序列。
     *  构建的原则是，从最右升起位，所有的左侧数中，找到比最右升起位大的最小数字，将之替换为最右升起位；
     *  这之后，将其余数字按照从小到大，逐个放置在各个位置。
     * ps: 如果不存在最右升起位，则说明不存在更大字典序列，此时仅需将序列原样逆序展示即可。
     *
     * 从以上信息可以得出，最方便的记录数据结构是栈，但要求是只允许使用额外常数空间，那就只能多遍历一次并cas了。
     *
     *
     * @param nums
     */
    public void nextPermutation(int[] nums) {
        if(nums.length==1){
            return;
        }
        int minUpIndex=0;
        for(int right=nums.length-1;right>=0;right--){
            if(right==0){
                reverseAll(nums,0,nums.length-1);
                return;
            }
            if(nums[right-1]<nums[right]){
                minUpIndex=right-1;
                break;
            }
        }

        int minUp=nums[minUpIndex];
        int newIndex;
        for(int right=nums.length-1;right>minUpIndex;right--){
            if(minUp<nums[right]){
                newIndex=right;
                cas(nums,newIndex,minUpIndex);
                reverseAll(nums,minUpIndex+1,nums.length-1);
                break;
            }
        }

    }

    private void reverseAll(int[] nums,int start,int end){
        for(int s=start,e=end;s<e;s++,e--){
            cas(nums,s,e);
        }
    }

    private void cas(int[] nums,int start,int end){
        int temp=nums[start];
        nums[start]=nums[end];
        nums[end]=temp;
    }
}
